# 破圈法：删除所有圈中权重最大的边

import copy
from tools.Conversion import Conversion
from tools.Graph import Graph
from tools.Input import Input
from tools.Output import Output


class BC:
    __name = 'Break Circle'

    @staticmethod
    def do_bc():
        # g = Input.input_graph()  # 输入无向图
        g = Input.get_graph1()  # 获取一个图（例3.2.1）
        print('输入的图为：')
        Output.print_graph_set(g)

        v_set = g[0]  # 图的点集
        s_set = g[1]  # 图的边集

        s_set = sorted(s_set.items(), key=lambda v: (v[1], v[0]), reverse=True)  # 对边集进行排序，降序排列

        tv_set = copy.deepcopy(v_set)  # 树的点集
        ts_set = copy.deepcopy(s_set)  # 树的边集

        print('生成过程：')
        for s in s_set:
            ts_set.remove(s)  # 取出权重最大的边
            new_graph = [tv_set, Conversion.arr2d_2_dict(ts_set)]  # 生成新的图
            result = Graph.ug_is_connected(new_graph)  # 图连通性判断
            if result:  # 去除边后，图连通
                print('去除边', s)
                continue
            ts_set.append(s)  # 将边加回去

        tree = [tv_set, Conversion.arr2d_2_dict(ts_set)]
        print('最小生成树为：')
        Output.print_graph_set(tree)
